package com.example.demo.test.leetcode.day1209;

public class Solution1209 {

    public static void main(String[] args) {
        System.out.println(uniquePaths(9, 51));
    }

    public static int uniquePaths(int m, int n) {
        // C(m+n-2,m-1) 7,3 ->  C(10-2,3-1) C(8,2) 8*7/2/1 =28
        // int a = Math.min(n, m) + 1;
        return (int) count(m + n - 2, Math.min(m, n) - 1);
    }

    public static long count(int m, int n) {
        if (n == 0)
            return 1;
        return m * count(m - 1, n - 1) / n;
    }


}
